package problem675;

//675.为高尔夫比赛砍树
//https://leetcode.cn/problems/cut-off-trees-for-golf-event/

import java.util.*;

class Solution {
    int n, m;
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};
    public int cutOffTree(List<List<Integer>> f) {
        n = f.size(); m = f.get(0).size();
        List<int[]> list = new ArrayList<>();
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(f.get(i).get(j) > 1) {
                    list.add(new int[] {i, j});
                }
            }
        }
        Collections.sort(list, (a, b)->f.get(a[0]).get(a[1]) - f.get(b[0]).get(b[1]));

        int ret = 0;
        int bx = 0, by = 0;
        for(int i = 0; i<list.size(); i++) {
            int ex = list.get(i)[0], ey = list.get(i)[1];
            int step = bfs(f, bx, by, ex, ey);
            if(step == -1) return -1;
            // System.out.println(step);
            ret += step;
            bx = ex;
            by = ey;
        }

        return ret;
    }

    public int bfs(List<List<Integer>> f, int bx, int by, int ex, int ey) {
        if(bx == ex && by == ey) return 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{bx, by});
        boolean[][] st = new boolean[n][m];
        st[bx][by] = true;
        int step = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            
            while(size -- > 0) {
                int[] t = queue.poll();
                int x = t[0], y = t[1];
                if(x == ex && y == ey) return step;
                for(int i = 0; i<4; i++) {
                    int dx = x + xx[i] , dy = y + yy[i];
                    if(dx >= 0 && dx < n && dy >= 0 && dy < m && !st[dx][dy] && f.get(dx).get(dy) != 0) {
                        st[dx][dy] = true;
                        queue.add(new int[]{dx, dy});
                    }
                }
            }
            step ++;
        }

        return -1;
    }
}

/*

2 3 4
9 0 5
8 7 6

*/